Knapsack Problem

The Knapsack Problem is a classic optimization problem that can be efficiently solved using dynamic programming. The goal is to choose a subset of items with maximum total value, subject to a weight constraint on the total weight of the chosen items.

Mathematical Formulation (0/1 Knapsack)

Given:

• $n$ items indexed from 1 to $n$
• $w_{i-1}$: weight of item $i$
• $v_{i-1}$: value of item $i$
• $cap$: maximum weight capacity of the knapsack

Objective:

• Maximize $\sum_{i=1}^n x_i v_{i-1}$

Subject to:

• $\sum_{i=1}^n x_i w_{i-1} \leq cap$
• $x_i \in \{0, 1\}$ for each $i$

Here, $x_i$ is a binary variable indicating whether item $i$ is included in the knapsack.

Dynamic Programming Approach

Define $dp[i, c]$ as the maximum value that can be achieved with the first $i$ items and a knapsack capacity of $c$.

State Transition:

• If item $i$ is not included.

$$dp[i, c] = dp[i-1, c]$$

• If item $i$ is included (only if $w_{i-1} \leq c$). $$dp[i, c] = \max(dp[i-1, c], dp[i-1, c-w_{i-1}] + v_{i-1})$$

Initialization:

• $dp[0, c] = 0$ for all $c$ (No items means no value).

Algorithm

1. Initialize a table $dp$ with dimensions $(n+1) \times (cap+1)$, all set to zero.
2. For each item $i$ from 1 to $n$:
   • For each capacity $c$ from 1 to $cap$:
     • If $w_{i-1} \leq c$, set $dp[i, c] = \max(dp[i-1, c], dp[i-1, c-w_{i-1}] + v_{i-1})$.
     • Otherwise, set $dp[i, c] = dp[i-1, c]$.
3. The value $dp[n, cap]$ will be the maximum value that fits into the knapsack.

Complexity

• Time Complexity: $O(n \times cap)$, where $n$ is the number of items and $cap$ is the capacity.
• Space Complexity: $O(n \times cap)$, although it can be reduced to $O(cap)$ using a 1-dimensional array if only the value is required, not the items themselves.

Implementation

A typical dynamic programming table fills in values iteratively for increasing item counts and capacities, ensuring all sub-problems are solved in a bottom-up manner.

Brute Force Search

The brute force approach explores every combination using recursion, evaluating the total value of all possible sets of items.

def knapsack_dfs(wgt, val, i, c):
    if i == 0 or c == 0:
        return 0
    if wgt[i-1] > c:
        return knapsack_dfs(wgt, val, i-1, c)
    no = knapsack_dfs(wgt, val, i-1, c)
    yes = knapsack_dfs(wgt, val, i-1, c-wgt[i-1]) + val[i-1]
    return max(no, yes)

Memoized Search

Enhances the brute force approach by storing results of sub-problems to avoid recomputation.

def knapsack_dfs_mem(wgt, val, mem, i, c):
    if i == 0 or c == 0:
        return 0
    if mem[i][c] != -1:
        return mem[i][c]
    if wgt[i-1] > c:
        return knapsack_dfs_mem(wgt, val, mem, i-1, c)
    no = knapsack_dfs_mem(wgt, val, mem, i-1, c)
    yes = knapsack_dfs_mem(wgt, val, mem, i-1, c-wgt[i-1]) + val[i-1]
    mem[i][c] = max(no, yes)
    return mem[i][c]

Space Optimization

The space complexity can be reduced by maintaining a single-dimensional array and updating values in reverse to prevent overwriting needed values for future states.

def knapsack_dp_comp(wgt, val, cap):
    dp = [0] * (cap + 1)
    for i in range(1, len(wgt) + 1):
        for c in range(cap, 0, -1):
            if wgt[i-1] <= c:
                dp[c] = max(dp[c], dp[c-wgt[i-1]] + val[i-1])
    return dp[cap]

Variants of the Knapsack Problem

1. 0/1 Knapsack Problem: Each item can either be taken or left (cannot be broken into smaller pieces). You must decide whether to include each item in the knapsack.
2. Fractional Knapsack Problem: Items can be divided into smaller parts. Thus, you can take fractions of items, which makes the problem easier and solvable by greedy algorithms.
3. Bounded Knapsack Problem: Each item can be included multiple times, but only up to a certain limit.
4. Unbounded Knapsack Problem: Each item can be taken multiple times without any limit.